#include<iostream>
using namespace std;

  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
 };
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;
        ListNode* start;
        if (list1->val < list2->val) {
            start = list1;
            start->next = mergeTwoLists(list1->next, list2);
        }
        else {
            start = list2;
            start->next = mergeTwoLists(list1, list2->next);
        }
        return start;
    }
    ListNode* sort(ListNode* now) {
        if (now == nullptr || now->next == nullptr)
            return now;
        ListNode* fast = now, * slow = now, * pre = nullptr;
        while (fast && fast->next) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        if (pre)
            pre->next = nullptr;
        return mergeTwoLists(sort(now), sort(slow));
    }
    ListNode* sortList(ListNode* head) {
        return sort(head);
    }
};
int main() {
    ListNode a1(4), a2(2), a3(1), a4(3);
    a1.next = &a2;
    a2.next = &a3;
    a3.next = &a4;
    a4.next = nullptr;
    Solution().sortList(&a1);
}